\documentclass{article}
\usepackage{amssymb,amsmath} % import math
\usepackage[german]{babel} % import german
\usepackage[applemac]{inputenc} % import german apple
\usepackage{graphicx} % import graphics

\title{HA2 - Uebung 1}
\author{Leonardo Balestrieri, Marco Traeger}

\begin{document}
\maketitle

\subsection*{1.1a}

Sei $x$ die Anzahl der Operationen, dann gilt nach dem Skript:
\begin{equation}
\begin{split}
				log_2 (7) 		&\geq log_3 x \\
\iff 				3^{log_2 (7)} 	&\geq x \\
\iff				3^{log_2 (7)}	& \approx 21.8498 \\
\Longrightarrow	x 			&\leq 21
\end{split}
\end{equation}
\\
Somit m"usste es $\leq 21$ Operationen ben"otigen.

\subsection*{1.1b}

Die Laufzeit berechnet sich $n^{log_k (p)}$, daher
\begin{itemize}
\item f"ur $k=68$ und $p=132464$ ist $log_{68} (132464) \approx 2.79512849$, 
daher ist die asymptotische Laufzeit des rekursiven Algorithmus ca. $O(n^{2.79512849})$
\item f"ur $k=70$ und $p=143640$ ist $log_{70} (143640) \approx 2.79512269$, 
daher ist die asymptotische Laufzeit des rekursiven Algorithmus ca. $O(n^{2.79512269})$
\item f"ur $k=72$ und $p=155424$ ist $log_{72} (155424) \approx 2.79514739$, , 
daher ist die asymptotische Laufzeit des rekursiven Algorithmus ca. $O(n^{2.79514739})$
\end{itemize}

\subsection*{1.1c}

Bei der Klassischen Multiplikation ben"otigt man genau $n^3$ Multiplikationen und $n^2*(n-1) = n^3-n^2$ Additionen.
Wir betrachten diese Operationen hier als im Rechenaufwand als gleichwertig, mit Laufzeit $1$.
Damit ist die Laufzeit des klassischen Algorithmus im Einheitsma"s: \\
\\
$M_C(n) = 2*n^3-n^2$ \\
\\
Beim Algorithmus von Strassen ist die Laufzeit im Einheitsma"s: \\
\\
$M_S(n) = n^{log(7)} + 4,5 \cdot n^2 \cdot \frac{ (\frac{7}{4})^{log(n)} - 1} {\frac{7}{4} - 1}$ \\
\\
Wir suchen also ein $N_0$, sodass:\\
\\
$\forall n \geq N_0 : M_S(n) \leq M_C(n) \wedge 2^k = n, k \in \mathbb{N}_0$

\begin{equation}
\begin{split}
M_C(n) & \geq M_S(n) \\
\iff &				2 \cdot n^3 - n^2 \geq n^{log(7)} + 4,5n^2 \cdot \frac{ (\frac{7}{4})^{log(n)} - 1} {\frac{7}{4} - 1} \\
\iff &				2 \cdot n^3 - n^2 \geq n^{log(7)} + 6n^2 \cdot ((\frac{7}{4})^{log(n)} - 1) \\
\iff &				2 \cdot n^3 - n^2 \geq n^{log(7)} + 6n^2 \cdot (\frac{7}{4})^{log(n)} - 6n^2 \\
\iff &				n^2 (2n + 5 - 6 \cdot 7^{log(\frac{7}{4})}) \geq n^{log 7} \\
\Longrightarrow &	n \geq 16.81 \\
\Longrightarrow &	n \geq 32 \iff N_0 = 32
\end{split}
\end{equation}

\subsection*{1.2a}

Berechnung von $\begin{pmatrix} I & A & 0 \\ 0 & I & B \\ 0 & 0 & I \end{pmatrix}^{-1}$.
\begin{equation}
\begin{split}
\left( \begin{matrix} I & A & 0 \\ 0 & I & B \\ 0 & 0 & I \end{matrix} \left| \begin{matrix} I & 0 & 0 \\ 0 & I & 0 \\ 0 & 0 & I \end{matrix} \right) \right. \\
\left( \begin{matrix} I & A & 0 \\ 0 & I & 0 \\ 0 & 0 & I \end{matrix} \left| \begin{matrix} I & 0 & 0 \\ 0 & I & -B \\ 0 & 0 & I \end{matrix} \right) \right. \\
\left( \begin{matrix} I & 0 & 0 \\ 0 & I & 0 \\ 0 & 0 & I \end{matrix} \left| \begin{matrix} I & -A & AB \\ 0 & I & -B \\ 0 & 0 & I \end{matrix} \right) \right.
\end{split}
\end{equation}
\\
Damit ist 
$$\begin{pmatrix} I & A & 0 \\ 0 & I & B \\ 0 & 0 & I \end{pmatrix}^{-1} = \begin{pmatrix} I & -A & AB \\ 0 & I & -B \\ 0 & 0 & I \end{pmatrix}$$
\\
Somit k"onnen wir $AB$ im oberen rechten Drittel der Inversen ablesen.
\\ \\
Damit ist die Multiplikation von 2 $n \times n$ Matrizen in Zeit $I(3n)$ m"oglich. Da man eine Matrix naive in polynomieller Zeit invertieren kann,
k"onnen wir auch davon ausgehen das $I(n)$ polynomiell ist. Daher:

$$ \forall n \geq 1:  I(3n) \leq I(3) * I(n) \in O(I(n))$$

\subsection*{1.2b}

Gegeben sind 2 $n \times n$-Matrizen $A$ und $B$, wir wollen $C=A \cdot B$ in $O(S(n))$ 
wobei wir eine $n \times n$-Matrix in S(n) Operationen quadrieren k"onnen.\\
\\
Wir nutzen folgenden Trick
$$
\begin{pmatrix} A & B \\ C & D \end{pmatrix} \cdot
\begin{pmatrix} A & B \\ C & D \end{pmatrix} =
\begin{pmatrix} AA + BC & AB + BD \\ CA + DC & CB + DD \end{pmatrix}
$$
Wir w"ahlen $C = 0$ und $D = 0$, dann gilt\\
$$
\begin{pmatrix} A & B \\ 0 & 0 \end{pmatrix}^2 = 
\begin{pmatrix} A & B \\ 0 & 0 \end{pmatrix} \cdot
\begin{pmatrix} A & B \\ 0 & 0 \end{pmatrix} =
\begin{pmatrix} AA & AB \\ 0 & 0 \end{pmatrix}
$$
Somit k"onnen wir $C=AB$ in der oberen linken Teilmatrix der Gr"o"se $n \times n$ ablesen, 
wenn wir die Matrix $\begin{pmatrix} A & B \\ 0 & 0 \end{pmatrix}$ quadrieren.\\
\\
Die zu quadierene Matrix hat die Gr"o"se $2n \times 2n$, somit ben"otigt die Multiplikation von A und B genau $S(2n)$ Operationen.
Die Quadrierung von $n \times n$ Matrizen ist naive in $O(n^3)$ m"oglich, daher k"onnen wir davon ausgehen, dass das hier vorausgesetzt
Verfahren mindestens so schnell ist, also unteranderem auch polynomiell. Damit ergibt sich: 

$$ \forall n \geq 1:  S(2n) \leq S(2) * S(n) \in O(S(n))$$

\subsection*{1.3a}
Auff"ullen bis zur n"achsten Zweierpotenz und anschlie"sende Verwendung des Algorithmus von Strassen.
\\\\
Laufzeit ist
$M_S(n) = n^{log(7)} + 4,5 \cdot n^2 \cdot \frac{ (\frac{7}{4})^{log(n)} - 1} {\frac{7}{4} - 1}$
wenn n Zweierpotenz.
\\ \\
Damit ergibt sich die Laufzeit bei Auff"ullen mit Nullen bei beliebigen $n$:
$$M_S(2^{\lceil log(n) \rceil})$$

\subsection*{1.3b}

\subsubsection*{Betrachtung des Ungeraden Falls}
$$
A \cdot B = \begin{pmatrix} A_{11}B_{11}+\overset{q_1}{A_{12}B_{21}} & \overset{q_2}{A_{11}B_{12}}+\overset{q_3}{A_{12}B_{22}} \\ 
\underset{q_4}{A_{21}B_{11}}+\underset{q_5}{A_{22}B_{21}} & \underset{q_6}{A_{21}B_{12}}+\underset{q_7}{A_{22}B_{22}} \end{pmatrix}
$$

\begin{equation}
\begin{split}
A_{12}, B_{12} \in M^{n-1,1} \\
A_{21}, B_{21} \in M^{1,n-1} \\
A_{22}, B_{22} \in M^{1,1}
\end{split}
\end{equation}

Laufzeiten f"ur die einzelnen Operationen:
\begin{equation}
\begin{split}
q_1 & = q(A_{12}B_{21}) = \overset{\text{Multiplikationen}}{(n-1)^2} \\
q_2 & = q(A_{11}B_{12}) = \overset{\text{Multiplikationen}}{(n-1)^2} + \overset{\text{Additionen}}{(n-1)(n-2)} \\
q_3 & = q(A_{12}B_{22}) = \overset{\text{Multiplikationen}}{n - 1} \\
q_4 & = q(A_{21}B_{11}) = \overset{\text{Multiplikationen}}{(n-1)^2} + \overset{\text{Additionen}}{(n-1)(n-2)} \\
q_5 & = q(A_{22}B_{21}) = \overset{\text{Multiplikationen}}{n-1} \\
q_6 & = q(A_{21}B_{12}) = \overset{\text{Multiplikationen}}{(n-1)} + \overset{\text{Additionen}}{(n-2)} \\
q_7 & = q(A_{22}B_{22}) = \overset{\text{Multiplikationen}}{1} \\
Q & = q_1+ ... + q_7 = 5n^2 - 8n + 3
\end{split}
\end{equation}

\subsubsection*{Laufzeit}
Damit ergibt sich die Laufzeit

\begin{equation}
\begin{split}
T(1)		&= 1 \\
T(n) 		& = \begin{cases} T_g(n) & n \text{ gerade} \\ T_u(n) & n \text{ ungerade} \end{cases} \\
T_g(n) 	& = 7*T(\frac{n}{2}) + 18(\frac{n}{2})^2 \text{ , Rekursionsschritt nach Strassen} \\
T_u(n) 	& = T(\frac{n-1}{2}) + Q + \overset{\text{Addition f"ur alle Teilmatrizen}}{n^2} \\
		& = T(\frac{n-1}{2}) + 5n^2 - 8n + 3 + n^2 \\
		& = T(\frac{n-1}{2}) + 6n^2 - 8n + 3 \\
\end{split}
\end{equation}

\begin{equation}
\begin{split}
T(1)		& = 1 \\
T(n) 		& \leq max(T_g(n), T_u(n)) \\
		& = max[7*T(\frac{n}{2}) + 18(\frac{n}{2})^2, T(\frac{n-1}{2}) + 6n^2 - 8n + 3] \\
		& \leq max[7*T(\frac{n}{2}), T(\frac{n-1}{2})] + max[18(\frac{n}{2})^2, 6n^2 - 8n + 3]
\end{split}
\end{equation}

\end{document}